from collections import defaultdict
from typing import List


class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        prefix = [0]
        for i in range(n):
            prefix.append((prefix[-1]+nums[i])%k)
        ha = defaultdict(set)
        ha[0].add(0)
        for i in range(n):
            p = prefix[i+1]
            # 相减要为k的倍数
            for index in ha[p]:
                if i - index >= 1: return True
            ha[nums[i]%k].add(i)
        return False



if __name__ == '__main__':
    s = Solution()
    r = s.checkSubarraySum( [1,0],2)
    print(r)